package com.chj.jz.dp.class05;

public class Code11_BackpackIII {
	/**
	 * @param m:
	 *            An integer m denotes the size of a backpack
	 * @param A:
	 *            Given n items with size A[i]
	 * @param V:
	 *            Given n items with value V[i]
	 * @return: The maximum value
	 */
	public static int backPackIII(int m, int[] A, int[] V) {
		// write your code here

		int n = A.length;
		if (n == 0) {
			return 0;
		}

		int[] f = new int[m + 1];
		int i, w;

		f[0] = 0;
		for (i = 1; i <= m; i++) {
			f[1] = -1;
		}

		for (i = 1; i <= n; i++) {
			for (w = 1; w <= m; w++) {
				if (w >= A[i - 1] && f[w - A[i - 1]] != -1) {
					f[w] = Math.max(f[w], f[w - A[i - 1]] + V[i - 1]);
				}
			}
		}

		int res = 0;
		for (w = 0; w <= m; w++) {
			if (f[w] != -1) {
				res = Math.max(res, f[w]);
			}
		}

		return res;

	}

	public static void main(String[] args) {
		{
			int[] arrK = new int[] { 2, 3, 5, 7 };
			int[] arrV = new int[] { 1, 5, 2, 4 };
			int k = 10;
			System.out.println(backPackIII(k, arrK, arrV));
		}
		{
			int[] arrK = new int[] { 2, 3, 8 };
			int[] arrV = new int[] { 2, 5, 8 };
			int k = 10;
			System.out.println(backPackIII(k, arrK, arrV));
		}
	}
}
